Today, many laser printers require that image data be available on demand for modulation of an imaging laser beam during printing of a page. In other words, once printing of a page has begun, there can be no delay or interruption of the stream of image pixel data to the laser modulator. This well known property is known in the art as page-synchronicity. Page-synchronicity is particularly common among monochromatic laser printers.
Many of the color laser printers of today retain a form of page-synchronicity as well. For example, when printing a page, most color laser printers image each of several color components, or color planes, in sequence and require that at least one entire color plane be immediately available to the laser modulator at any given time. In other words, a first color plane (e.g., cyan) is sent to the printer and imaged onto a photoconductor, and then the next color plane (e.g., magenta) is sent to the printer and imaged, and so forth. During imaging of each plane, pixel data for the entire plane must be immediately available. Though some color laser devices of today are truly page synchronous (i.e., they require that data for all planes be immediately available during printing of a page), the more recent models are plane-synchronous in nature (i.e., there can be an indefinite pause between data transmission of each plane).
Due to this page- or plane-synchronous property of laser printers, pixel data for a page or a plane must be either (a) rendered and rasterized, or otherwise created, in real time (and at high speed) during printing of the page or plane, or (b) pre-rendered and stored in an image frame memory before the first pixel is sent to the laser printer. Real-time, or race, rasterization of pixel data is an operation which is unbounded in time. In other words, because pages and planes can be arbitrarily complex, the time required to render a page or plane cannot be known a priori. Thus, real-time rasterization hardware and software must be fast enough to account for peak data rates. However, because such high-speed resources can be prohibitively expensive, real-time rasterization is often not a practical design option.
Alternatively, if an entire page or plane is pre-rendered into memory, then assuming the memory subsystem is fast enough that stored data can be read back at the pixel rate required by the laser modulator, the rasterization hardware and software need not operate at real-time rates. As a result, many systems of today are constructed to utilize pre-rendering techniques. However, the memory required for full-frame buffer rendering (i.e., storage of an entire page or plane) can also be quite expensive given the high resolution of today's laser printers. For example, at 600 dpi, letter-sized bi-level black and white printers require 4 MB of storage per page. Additionally, 8-bit-per-pixel Cyan-Magenta-Yellow-Black (CMYK) color printers require 128 MB of storage per 600 dpi letter-sized page.
Thus, systems are now being built in which data compression techniques are used to minimize the memory needed to store pre-rendered images. In other words, a rendered page or plane is compressed as it is being generated so that the memory required to store the resulting image is reduced. Since known data compression methods provide bounded decompression times, decompression of the data can be done in real-time during printing to satisfy the page or plane synchronicity requirements of the printer.
However, known methods of compression require that a system designer compromise between maximum data throughput and minimum memory cost. This is due to the fact that certain known compression techniques result in relatively small peak memory requirements and relatively large average memory requirements during printing (corresponding to relatively low memory cost and relatively low data throughput, respectively), while other known compression techniques result in relatively large peak memory requirements and relatively small average memory requirements during printing (corresponding to relatively high memory cost and relatively high data throughput, respectively).
However, because higher system throughput and lower system cost are always desirable, it would be advantageous if a system designer could minimize both peak and average memory requirements simultaneously. Thus, there is a need for improved methods and apparatus for compressing data and for managing memory storage of compressed data.